﻿#include <iostream>

struct JosephRingNode
{
	int value;
	JosephRingNode* next;
};

/**
 * 使用环形单链表模拟约瑟夫环
 */
static int simulateJosephRingByLinkedList(int nodeCount, int m)
{
	JosephRingNode* head = new JosephRingNode;
	head->value = 1;
	JosephRingNode* cur = head;
	JosephRingNode* last = nullptr;
	for (int i = 0; i < nodeCount - 1; i++)
	{
		cur->next = new JosephRingNode;
		cur->next->value = cur->value + 1;
		last = cur->next;
		cur = cur->next;
	}

	last->next = head;

	cur = head;
	JosephRingNode* prev = last;
	JosephRingNode* next = nullptr;
	int index = 0;
	while (cur->next != cur)
	{
		++index;
		if (index == m)
		{
			next = cur->next;
			prev->next = next;
			delete(cur);
			cur = next;
			index = 0;
		}
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}

	return cur->value;
}

/**
 * 基于: y = x % i
 * 推出的公式
 */
static int useFunction(int i, int m)
{
	if (i == 1) return 1;

	return (useFunction(i - 1, m) + m - 1) % i + 1;
}

/**
 * 约瑟夫环问题
 * 有n个节点组成一个环形单链表：
 * ...->node1->node2->node3->...->nodeN->node1->...
 * 从node1开始由1报数，每走一个节点报比前一个节点大1的数，直到报到m，则删除当前报m的节点，然后上一个节点指向被删除节点的下一个节点，下一个节点再从1开始报数，再遇到m，把报m的节点删除，再将前后节点连起来，周而往复，直到最后剩下一个节点，即为所要求的节点。
 * 
 * 思路：
 * 1. 基于公式: y = x % i
 * 推出节点编号和报数之间的关系: y = (x - 1) % i + 1 
 *    其中，y代表节点编号(1号->2号->3号->...->i号); x代表节点的报数；i代表节点个数
 * 
 * 举例：假设有一个环形单链表，一共有5个节点，
 *  编号   报数
 *   1     1
 *   2     2
 *   3     3
 *   4     4
 *   5     5
 *   1     6
 *   2     7
 *   3     8
 *  ...   ...
 *   i     i
 *  ...   ...
 *   1    i+1
 *  ...   ...
 *   2i    2i
 * 
 * 2. 基于公式: y = x % i
 * 又可以推出新旧节点编号之间的关系：y = (x - 1 + S) % i + 1
 *    其中，y代表删除节点之前的旧编号，x代表删除节点之后的新编号，S代表报数报到多少就删除一个节点，即被删除节点的编号，i代表删除节点之后的节点个数
 *    S又可以根据上一步的公式推出：y = (x - 1) % i + 1 ，则有：
 * S = (m - 1) % i + 1
 * 再代入S， y = (x - 1 + (m - 1) % i + 1) % i + 1
 * 化简得：
 * y = (x + m - 1) % i + 1
 * 
 */
int main_josephRing()
{
	int originalNodeCount = 18;
	int m = 7;

	int lastNodeValue = simulateJosephRingByLinkedList(originalNodeCount, m);
	printf("use ring linked list: %d\n", lastNodeValue);
	int res = useFunction(originalNodeCount, m);
	printf("useFunction: %d\n", res);
	return 0;
}